{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #交易逆序对的总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reversePairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交易逆序对的总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 <code>record</code>，返回其中存在的「交易逆序对」总数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>record = [9, 7, 5, 4, 6]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<p><code>0 &lt;= record.length &lt;= 50000</code></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zu-zhong-de-ni-xu-dui-lcof](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zu-zhong-de-ni-xu-dui-lcof](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge_sort(self, l, r):\n",
    "        if l >= r:\n",
    "            return 0\n",
    "        mid = (l + r) // 2\n",
    "        ret = 0\n",
    "        ret += self.merge_sort(l, mid)\n",
    "        ret += self.merge_sort(mid + 1, r)\n",
    "        new_nums = []\n",
    "        pos1 = l\n",
    "        pos2 = mid + 1\n",
    "        while (pos1 <= mid or pos2 <= r):\n",
    "            if pos1 > mid:\n",
    "                new_nums.append(self.nums[pos2])\n",
    "                pos2 += 1\n",
    "            elif pos2 > r:\n",
    "                new_nums.append(self.nums[pos1])\n",
    "                pos1 += 1\n",
    "            elif self.nums[pos1] > self.nums[pos2]:\n",
    "                new_nums.append(self.nums[pos2])\n",
    "                pos2 += 1\n",
    "                ret += mid - pos1 + 1\n",
    "            elif self.nums[pos1] < self.nums[pos2]:\n",
    "                new_nums.append(self.nums[pos1])\n",
    "                pos1 += 1\n",
    "            else:\n",
    "                new_nums.append(self.nums[pos1])\n",
    "                pos1 += 1\n",
    "        self.nums[l:r+1] = new_nums\n",
    "        return ret\n",
    "\n",
    "    def reversePairs(self, nums) -> int:\n",
    "        self.nums = nums\n",
    "        return self.merge_sort(0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        import bisect\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        tmp = [nums[-1]]\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            k = bisect.bisect_left(tmp, nums[i])\n",
    "            res += k\n",
    "            tmp.insert(k, nums[i])\n",
    "        return res\n",
    "\n",
    "        # if nums == []:\n",
    "        #     return 0\n",
    "        # tmp = [nums[-1]]\n",
    "        # res = 0\n",
    "        # for i in range(len(nums)-2,-1,-1):\n",
    "        #     left = 0\n",
    "        #     right = len(tmp)-1\n",
    "        #     mid = 0\n",
    "        #     k = 0\n",
    "        #     while left < right:\n",
    "        #         mid = (left+right) // 2\n",
    "        #         if tmp[mid] < nums[i]:\n",
    "        #             left = mid+1\n",
    "        #         else:\n",
    "        #             right = mid-1\n",
    "        #     if tmp[left]<nums[i]:\n",
    "        #         k = left + 1\n",
    "        #     elif tmp[right] <\n",
    "        #     print(left, right, mid, k, tmp)\n",
    "        #     res += k\n",
    "        #     tmp.insert(k, nums[i])\n",
    "\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        count = 0\n",
    "        tmp = []\n",
    "        for num in reversed(record):\n",
    "            ind = bisect.bisect_left(tmp, num)\n",
    "            count += ind \n",
    "            tmp.insert(ind, num)\n",
    "        return count  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        count = 0\n",
    "        tmp = []\n",
    "        for num in reversed(record):\n",
    "            ind = bisect.bisect_left(tmp, num)\n",
    "            count += ind \n",
    "            tmp.insert(ind, num)\n",
    "        return count  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge_count(self,l1,l2):\n",
    "        l1.sort()\n",
    "        l2.sort()\n",
    "        res=0\n",
    "        i=j=0\n",
    "        while i<len(l1) and j<len(l2):\n",
    "            if l1[i]<=l2[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                res+=(len(l1)-i)\n",
    "                j+=1\n",
    "        return res\n",
    "    def reversePairs(self,record: list[int]) -> int:\n",
    "        length = len(record)\n",
    "        res=0\n",
    "        if length>1:\n",
    "            mid=int(length/2)\n",
    "            l1=record[0:mid]\n",
    "            l2=record[mid:length]\n",
    "            res=self.reversePairs(l1)+self.reversePairs(l2)\n",
    "            res+=self.merge_count(l1,l2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        if len(record) <=1:return 0\n",
    "        stack, c = [record[0]],0\n",
    "        for num in record[1:]:\n",
    "            index = bisect.bisect_right(stack, num)\n",
    "            c += len(stack)-index\n",
    "            bisect.insort_right(stack, num)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        # 归并排序\n",
    "        ans=0\n",
    "        def mergeSort(record,l,r):\n",
    "            nonlocal ans\n",
    "            if l>=r:\n",
    "                return\n",
    "            m=(l+r)//2\n",
    "            mergeSort(record,l,m)\n",
    "            mergeSort(record,m+1,r)\n",
    "            # [l,m]有序[m+1,r]有序\n",
    "            bank=[]\n",
    "            pl=l\n",
    "            pr=m+1\n",
    "            while pl<=m and pr<=r:\n",
    "                if record[pl]>record[pr]:\n",
    "                    bank.append(record[pl])\n",
    "                    ans+=r-pr+1\n",
    "                    pl+=1\n",
    "                else:\n",
    "                    bank.append(record[pr])\n",
    "                    pr+=1\n",
    "            while pl<=m:\n",
    "                bank.append(record[pl])\n",
    "                pl+=1\n",
    "            while pr<=r:\n",
    "                bank.append(record[pr])\n",
    "                pr+=1\n",
    "            for i in range(l,r+1):\n",
    "                record[i]=bank[i-l]\n",
    "        \n",
    "        mergeSort(record,0,len(record)-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        cnt=[0]\n",
    "        def MergeSort(arr, L, R):\n",
    "            if L >= R:\n",
    "                return\n",
    "            \n",
    "            M = L + int((R-L)/2)\n",
    "            MergeSort(arr, L, M)\n",
    "            MergeSort(arr, M+1, R)\n",
    "            \n",
    "            p1, p2 = L, M+1\n",
    "            tmp = []\n",
    "            while p1 <= M and p2 <= R:\n",
    "                if arr[p1]<=arr[p2]:\n",
    "                    tmp.append(arr[p1])\n",
    "                    p1 += 1\n",
    "                else:\n",
    "                    tmp.append(arr[p2])\n",
    "                    cnt[0] += M-p1+1\n",
    "                    p2 += 1\n",
    "                \n",
    "            while p1 <= M:\n",
    "                tmp.append(arr[p1])\n",
    "                p1 += 1\n",
    "            \n",
    "            while p2 <= R:\n",
    "                tmp.append(arr[p2])\n",
    "                p2 += 1\n",
    "\n",
    "            for k in range(len(tmp)):\n",
    "                arr[L+k]=tmp[k]\n",
    "\n",
    "            return  \n",
    "        \n",
    "        MergeSort(nums, 0, len(nums)-1)\n",
    "        return cnt[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        self.tmp = []\n",
    "    # 包装方法\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        # 执行归并排序\n",
    "        self.mergeSort(nums, 0, len(nums) - 1)\n",
    "        return self.count\n",
    "    # 归并排序\n",
    "    def mergeSort(self, nums, left, right):\n",
    "        if left >= right:\n",
    "            return\n",
    "        mid = left + (right - left) // 2\n",
    "        self.mergeSort(nums, left, mid)\n",
    "        self.mergeSort(nums, mid + 1, right)\n",
    "        self.merge(nums, left, mid, right)\n",
    "    # 合并两个有序数组\n",
    "    def merge(self, nums, left, mid, right):\n",
    "        i, j = left, mid + 1\n",
    "        t = []\n",
    "        while i <= mid and j <= right:\n",
    "            if nums[i] <= nums[j]:\n",
    "                t.append(nums[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                t.append(nums[j])\n",
    "                j += 1\n",
    "                # 当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，\n",
    "                # 此时这个数就是，逆序数\n",
    "                # 定义一个计数器，记下每次合并中存在的逆序数。\n",
    "                self.count += (mid - i + 1)\n",
    "        while i <= mid:\n",
    "            t.append(nums[i])\n",
    "            i += 1\n",
    "        while j <= right:\n",
    "            t.append(nums[j])\n",
    "            j += 1\n",
    "        nums[left:right + 1] = t\n",
    "\n",
    "# # 上述算法在mergeSort中我们每次都开辟一个新的temp，这样空间复杂度大概相当于NlogN，实际上我们完全每必要每次mergeSort都开辟一个新的，而是大家也都用一个。\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.count = 0\n",
    "#         self.t = []\n",
    "#     # 包装方法\n",
    "#     def reversePairs(self, nums: List[int]) -> int:\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "#         # 执行归并排序\n",
    "#         self.mergeSort(nums, 0, len(nums) - 1)\n",
    "#         return self.count\n",
    "#     # 归并排序\n",
    "#     def mergeSort(self, nums, left, right):\n",
    "#         if left >= right:\n",
    "#             return\n",
    "#         mid = left + (right - left) // 2\n",
    "#         self.mergeSort(nums, left, mid)\n",
    "#         self.mergeSort(nums, mid + 1, right)\n",
    "#         self.merge(nums, left, mid, right)\n",
    "#     # 合并两个有序数组\n",
    "#     def merge(self, nums, left, mid, right):\n",
    "#         i, j = left, mid + 1\n",
    "#         while i <= mid and j <= right:\n",
    "#             if nums[i] <= nums[j]:\n",
    "#                 self.t.append(nums[i])\n",
    "#                 i += 1\n",
    "#             else:\n",
    "#                 self.t.append(nums[j])\n",
    "#                 j += 1\n",
    "#                 # 当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，\n",
    "#                 # 此时这个数就是，逆序数\n",
    "#                 # 定义一个计数器，记下每次合并中存在的逆序数。\n",
    "#                 self.count += (mid - i + 1)\n",
    "#         while i <= mid:\n",
    "#             self.t.append(nums[i])\n",
    "#             i += 1\n",
    "#         while j <= right:\n",
    "#             self.t.append(nums[j])\n",
    "#             j += 1\n",
    "#         nums[left:right + 1] = self.t\n",
    "#         self.t.clear()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        # write code here\n",
    "        n = len(record)\n",
    "        res = [0] * n\n",
    "        return self.MergeSort(0, n-1, record, res)\n",
    "    \n",
    "    def MergeSort(self, left:int, right:int, data:List[int], temp:List[int]):\n",
    "        if left >= right:\n",
    "            return 0\n",
    "        mid = int((left+right) / 2)\n",
    "        res = self.MergeSort(left, mid, data, temp) + self.MergeSort(mid+1, right, data, temp)\n",
    "        # res %= 1000000007\n",
    "        \n",
    "\n",
    "        i, j = left, mid + 1\n",
    "        # for k in range(left, right + 1):\n",
    "        #     temp[k] = data[k]\n",
    "        temp = []\n",
    "        while i <= mid and j <= right:\n",
    "            if data[i] <= data[j]:\n",
    "                temp.append(data[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                temp.append(data[j])\n",
    "                j += 1\n",
    "                res += (mid - i + 1)\n",
    "        while i <= mid:\n",
    "            temp.append(data[i])\n",
    "            i += 1\n",
    "        while j <= right:\n",
    "            temp.append(data[j])\n",
    "            j += 1\n",
    "        for k in range(len(temp)):\n",
    "            data[left + k] = temp[k]\n",
    "        # nums[left:right+1] = temp\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeSort(self, nums, temp, left, right):\n",
    "\n",
    "        if left >= right:\n",
    "            return 0 \n",
    "        mid = (left + right) // 2\n",
    "        reversePairsCnt = self.mergeSort(nums, temp, left, mid) + self.mergeSort(nums, temp, mid+1, right)\n",
    "        i, j, pos = left, mid+1, left\n",
    "        while i <= mid and j <= right:\n",
    "            if nums[i] <= nums[j]:\n",
    "                temp[pos] = nums[i]\n",
    "                i += 1\n",
    "                reversePairsCnt += (j - mid - 1)\n",
    "            else:\n",
    "                temp[pos] = nums[j]\n",
    "                j += 1\n",
    "            pos += 1\n",
    "        for x in nums[i:mid+1]: \n",
    "            temp[pos] = x\n",
    "            pos += 1\n",
    "            reversePairsCnt += (j - mid - 1)\n",
    "        for x in nums[j:right+1]:\n",
    "            temp[pos] = x\n",
    "            pos += 1\n",
    "\n",
    "        nums[left:right+1] = temp[left:right+1] \n",
    "        return reversePairsCnt\n",
    "\n",
    "    def reversePairs(self, nums):\n",
    "        return self.mergeSort(nums, [0]*len(nums), 0, len(nums)-1)\n",
    "    def reversePairs_(self, nums: List[int]):\n",
    "        self.res = 0\n",
    "        def merge(list1, list2):\n",
    "            l1 = l2 = 0\n",
    "            merge_res = []\n",
    "            while l1 < len(list1) and l2 < len(list2):\n",
    "                if list1[l1] <= list2[l2]:\n",
    "                    merge_res.append(list1[l1])\n",
    "                    l1 += 1\n",
    "                else:\n",
    "                    # self.res += (len(list1) - l1)\n",
    "                    self.res += len(list1[l1:])\n",
    "                    merge_res.append(list2[l2])\n",
    "                    l2 += 1\n",
    "            merge_res.extend(list1[l1:] or list2[l2:])\n",
    "            return merge_res\n",
    "        \n",
    "        def merge_sort(nums_input):\n",
    "            length = len(nums_input)\n",
    "            if length <= 1:\n",
    "                return nums_input\n",
    "            mid = length // 2\n",
    "            left = merge_sort(nums_input[:mid])\n",
    "            right = merge_sort(nums_input[mid:])\n",
    "            return merge(left, right)\n",
    "        merge_sort(nums)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexTree:\n",
    "    __slots__ = ['size', 'tree']\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.size = n \n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & -x\n",
    "\n",
    "    def query(self, x: int) ->int:\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x -= BinaryIndexTree.lowbit(x)\n",
    "        return res\n",
    "\n",
    "    def update(self, x: int) -> None:\n",
    "        while x <= self.size:\n",
    "            self.tree[x] += 1\n",
    "            x += BinaryIndexTree.lowbit(x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        n = len(record)\n",
    "\n",
    "        # 离散化(不去重)\n",
    "\n",
    "        tmp = sorted(record)\n",
    "        for i in range(n):\n",
    "            record[i] = bisect_left(tmp, record[i]) + 1\n",
    "\n",
    "        # 树状数组统计逆序对\n",
    "        res = 0\n",
    "        bit = BinaryIndexTree(n)\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res += bit.query(record[i] - 1)\n",
    "            bit.update(record[i])\n",
    "\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2: return 0\n",
    "        if len(nums) == 2 :return 1 if nums[0] > nums[1] else 0\n",
    "        count, centercount = 0, 0\n",
    "        bigger, less = [], []\n",
    "        mid = nums[int(len(nums)/2)]\n",
    "        for num in nums:\n",
    "            if num < mid:\n",
    "                less.append(num)\n",
    "                count += len(bigger)\n",
    "                count += centercount\n",
    "            elif num > mid:\n",
    "                bigger.append(num)\n",
    "            else:\n",
    "                centercount += 1\n",
    "                count += len(bigger)\n",
    "        count += self.reversePairs(less)\n",
    "        count += self.reversePairs(bigger)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    cnt = 0\n",
    "    def merge(self, left_arr, right_arr):           # 归并过程\n",
    "        arr = []\n",
    "        left_i, right_i = 0, 0\n",
    "        while left_i < len(left_arr) and right_i < len(right_arr):\n",
    "            # 将两个有序子序列中较小元素依次插入到结果数组中\n",
    "            if left_arr[left_i] <= right_arr[right_i]:\n",
    "                arr.append(left_arr[left_i])\n",
    "                left_i += 1\n",
    "            else:\n",
    "                self.cnt += len(left_arr) - left_i\n",
    "                arr.append(right_arr[right_i])\n",
    "                right_i += 1\n",
    "        \n",
    "        while left_i < len(left_arr):\n",
    "            # 如果左子序列有剩余元素，则将其插入到结果数组中\n",
    "            arr.append(left_arr[left_i])\n",
    "            left_i += 1\n",
    "            \n",
    "        while right_i < len(right_arr):\n",
    "            # 如果右子序列有剩余元素，则将其插入到结果数组中\n",
    "            arr.append(right_arr[right_i])\n",
    "            right_i += 1\n",
    "        \n",
    "        return arr                                  # 返回排好序的结果数组\n",
    "\n",
    "    def mergeSort(self, arr):                       # 分割过程\n",
    "        if len(arr) <= 1:                           # 数组元素个数小于等于 1 时，直接返回原数组\n",
    "            return arr\n",
    "        \n",
    "        mid = len(arr) // 2                         # 将数组从中间位置分为左右两个数组。\n",
    "        left_arr = self.mergeSort(arr[0: mid])      # 递归将左子序列进行分割和排序\n",
    "        right_arr =  self.mergeSort(arr[mid:])      # 递归将右子序列进行分割和排序\n",
    "        return self.merge(left_arr, right_arr)      # 把当前序列组中有序子序列逐层向上，进行两两合并。\n",
    "\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.cnt = 0\n",
    "        self.mergeSort(nums)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        l = SortedList()\n",
    "        s = 0\n",
    "        for r in record:\n",
    "            r = -r\n",
    "            l.add(r)\n",
    "            s += l.index(r)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def sort_process(record: List[int], left: int, right: int) -> List[int]:\n",
    "            if left == right:\n",
    "                return [record[left]]\n",
    "            mid = (left + right) // 2\n",
    "            left_l = sort_process(record, left, mid)\n",
    "            right_l = sort_process(record, mid + 1, right)\n",
    "            return merge(left_l, right_l)\n",
    "\n",
    "        def merge(nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "            nonlocal ans\n",
    "            l1 = 0\n",
    "            n1 = len(nums1)\n",
    "            l2 = 0\n",
    "            n2 = len(nums2)\n",
    "            info = []\n",
    "\n",
    "            while l1 < n1 and l2 < n2:\n",
    "                if nums1[l1] <= nums2[l2]:\n",
    "                    info.append(nums1[l1])\n",
    "                    l1 += 1\n",
    "                else:\n",
    "                    ans += n1 - l1\n",
    "                    info.append(nums2[l2])\n",
    "                    l2 += 1\n",
    "\n",
    "            if l1 < n1:\n",
    "                info += nums1[l1:]\n",
    "            if l2 < n2:\n",
    "                info += nums2[l2:]\n",
    "            return info\n",
    "\n",
    "        if not record:\n",
    "            return 0\n",
    "        sort_process(record, 0, len(record) - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def merge_sort(self, arr: List[int]):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        mid = len(arr) // 2\n",
    "        left_arr = arr[:mid]\n",
    "        right_arr = arr[mid:]\n",
    "        left_half = self.merge_sort(left_arr)\n",
    "        right_half = self.merge_sort(right_arr)\n",
    "        return self.merge(left_half, right_half)\n",
    "\n",
    "    def merge(self, left_arr, right_arr):\n",
    "        merged = []\n",
    "        left_index, right_index = 0, 0\n",
    "        while left_index < len(left_arr) and right_index < len(right_arr):\n",
    "            if left_arr[left_index] <= right_arr[right_index]:\n",
    "                merged.append(left_arr[left_index])\n",
    "                left_index += 1\n",
    "            else:\n",
    "                merged.append(right_arr[right_index])\n",
    "                right_index += 1\n",
    "                self.ans += (len(left_arr) - left_index)\n",
    "        merged.extend(left_arr[left_index:])\n",
    "        merged.extend(right_arr[right_index:])\n",
    "\n",
    "        return merged\n",
    "\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        self.merge_sort(record)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "\n",
    "        def sort_merge(l1, l2):\n",
    "            count = 0\n",
    "            merged = []\n",
    "            l1_index, l2_index = 0, 0\n",
    "            while l1_index < len(l1) and l2_index < len(l2):\n",
    "                if l1[l1_index] <= l2[l2_index]:\n",
    "                    merged.append(l1[l1_index])\n",
    "                    l1_index += 1\n",
    "                else:\n",
    "                    merged.append(l2[l2_index])\n",
    "                    l2_index += 1\n",
    "                    count += (len(l1) - l1_index)\n",
    "\n",
    "            merged.extend(l1[l1_index:])\n",
    "            merged.extend(l2[l2_index:])\n",
    "\n",
    "            return merged, count\n",
    "\n",
    "        def parition_sort(nums: List[int]):\n",
    "            if len(nums) <= 1:\n",
    "                return nums, 0\n",
    "            mid = len(nums)//2\n",
    "            left = nums[:mid]\n",
    "            right = nums[mid:]\n",
    "\n",
    "            left_arr, left_count = parition_sort(left)\n",
    "            right_arr, right_count = parition_sort(right)\n",
    "\n",
    "            merged, merge_count = sort_merge(left_arr, right_arr)\n",
    "            return merged, merge_count + left_count + right_count\n",
    "        _, ans = parition_sort(record)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    ans = 0\n",
    "\n",
    "    def sort_merge(self, arr: List[int]):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        mid = len(arr) // 2\n",
    "        left_arr = arr[:mid]\n",
    "        right_arr = arr[mid:]\n",
    "\n",
    "        left_half = self.sort_merge(left_arr)\n",
    "        right_half = self.sort_merge(right_arr)\n",
    "        return self.merge(left_half, right_half)\n",
    "\n",
    "    def merge(self, l1: List[int], l2: List[int]):\n",
    "        merged = []\n",
    "        l1_index, l2_index = 0, 0\n",
    "        while l1_index < len(l1) and l2_index < len(l2):\n",
    "            if l1[l1_index] <= l2[l2_index]:\n",
    "                merged.append(l1[l1_index])\n",
    "                l1_index += 1\n",
    "            else:\n",
    "                self.ans += (len(l1) - l1_index)\n",
    "                merged.append(l2[l2_index])\n",
    "                l2_index += 1\n",
    "        merged.extend(l1[l1_index:])\n",
    "        merged.extend(l2[l2_index:])\n",
    "\n",
    "        return merged\n",
    "\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        self.sort_merge(record)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    count=0\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.mergesort(nums)\n",
    "        return self.count\n",
    "        \n",
    "    def mergesort(self, nums):\n",
    "        if len(nums)<2:\n",
    "            return nums\n",
    "        mid=(len(nums)+1)//2\n",
    "        left=self.mergesort(nums[:mid])\n",
    "        right=self.mergesort(nums[mid:])\n",
    "        tmplist=[]\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<len(left) and j<len(right):\n",
    "            if left[i]<=right[j]:\n",
    "                tmplist.append(left[i])\n",
    "                i+=1\n",
    "            else:\n",
    "                self.count+=len(left)-i\n",
    "                tmplist.append(right[j])\n",
    "                j+=1\n",
    "        return tmplist+left[i:]+right[j:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    ans = 0\n",
    "\n",
    "    def partition(self, nums: List[int]):\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "        mid = len(nums)//2\n",
    "        left = nums[:mid]\n",
    "        right = nums[mid:]\n",
    "\n",
    "        left_arr = self.partition(left)\n",
    "        right_arr = self.partition(right)\n",
    "        return self.merge_sort(left_arr, right_arr)\n",
    "\n",
    "    def merge_sort(self, left_arr, right_arr):\n",
    "        merged = []\n",
    "        left_index, right_index = 0, 0\n",
    "        while left_index < len(left_arr) and right_index < len(right_arr):\n",
    "            if left_arr[left_index] <= right_arr[right_index]:\n",
    "                merged.append(left_arr[left_index])\n",
    "                left_index += 1\n",
    "            else:\n",
    "                merged.append(right_arr[right_index])\n",
    "                right_index += 1\n",
    "                self.ans += (len(left_arr) - left_index)\n",
    "\n",
    "        merged.extend(left_arr[left_index:])\n",
    "        merged.extend(right_arr[right_index:])\n",
    "\n",
    "        return merged\n",
    "\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        print(self.partition(record))\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "  def reversePairs(self, record: List[int]) -> int:\n",
    "    n = len(record)\n",
    "    b = sorted(set(record))\n",
    "    bit = BIT(len(b))\n",
    "    ans = 0\n",
    "    for i in range(n - 1, -1, -1):\n",
    "      j = bisect_left(b, record[i]) + 1\n",
    "      ans += bit.query(j - 1)\n",
    "      bit.update(j)\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length < 2:\n",
    "            return 0\n",
    "        global cmp_nums\n",
    "        cmp_nums = list(range(length))\n",
    "        return self.merge_sort(nums, 0, len(nums)-1)\n",
    "        \n",
    "    \n",
    "    def merge_sort(self, nums, left, right):\n",
    "        if left == right:\n",
    "            return 0\n",
    "        mid = left + (right - left) // 2\n",
    "        left_reverse_pairs = self.merge_sort(nums, left, mid)\n",
    "        right_reverse_pairs = self.merge_sort(nums, mid+1, right)\n",
    "        if nums[mid] <= nums[mid+1]:\n",
    "            return left_reverse_pairs + right_reverse_pairs\n",
    "        return left_reverse_pairs + right_reverse_pairs + self.merge_two_sorted_arrs(nums, left, mid, right)\n",
    "\n",
    "    def merge_two_sorted_arrs(self, nums, left, mid, right):\n",
    "        for i in range(left, right+1):\n",
    "            cmp_nums[i] = nums[i] \n",
    "        i, j = left, mid+1\n",
    "        result = 0\n",
    "        for k in range(left, right+1):\n",
    "            if i > mid:\n",
    "                nums[k] = cmp_nums[j]\n",
    "                j += 1\n",
    "            elif j > right:\n",
    "                nums[k] = cmp_nums[i]\n",
    "                i += 1\n",
    "            elif cmp_nums[i] <= cmp_nums[j]:\n",
    "                nums[k] = cmp_nums[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                nums[k] = nums[j]\n",
    "                j += 1\n",
    "                result += mid-i+1\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "\n",
    "#     def reversePairs(self, nums: List[int]) -> int:\n",
    "#         size = len(nums)\n",
    "#         if size < 2:\n",
    "#             return 0\n",
    "\n",
    "#         # 用于归并的辅助数组\n",
    "#         temp = [0 for _ in range(size)]\n",
    "#         return self.count_reverse_pairs(nums, 0, size - 1, temp)\n",
    "\n",
    "#     def count_reverse_pairs(self, nums, left, right, temp):\n",
    "#         # 在数组 nums 的区间 [left, right] 统计逆序对\n",
    "#         if left == right:\n",
    "#             return 0\n",
    "#         mid = (left + right) >> 1\n",
    "#         left_pairs = self.count_reverse_pairs(nums, left, mid, temp)\n",
    "#         right_pairs = self.count_reverse_pairs(nums, mid + 1, right, temp)\n",
    "\n",
    "#         reverse_pairs = left_pairs + right_pairs\n",
    "#         # 代码走到这里的时候，[left, mid] 和 [mid + 1, right] 已经完成了排序并且计算好逆序对\n",
    "\n",
    "#         if nums[mid] <= nums[mid + 1]:\n",
    "#             # 此时不用计算横跨两个区间的逆序对，直接返回 reverse_pairs\n",
    "#             return reverse_pairs\n",
    "\n",
    "#         reverse_cross_pairs = self.merge_and_count(nums, left, mid, right, temp)\n",
    "#         return reverse_pairs + reverse_cross_pairs\n",
    "\n",
    "#     def merge_and_count(self, nums, left, mid, right, temp):\n",
    "#         \"\"\"\n",
    "#         [left, mid] 有序，[mid + 1, right] 有序\n",
    "\n",
    "#         前：[2, 3, 5, 8]，后：[4, 6, 7, 12]\n",
    "#         只在后面数组元素出列的时候，数一数前面这个数组还剩下多少个数字，\n",
    "#         由于\"前\"数组和\"后\"数组都有序，\n",
    "#         此时\"前\"数组剩下的元素个数 mid - i + 1 就是与\"后\"数组元素出列的这个元素构成的逆序对个数\n",
    "\n",
    "#         \"\"\"\n",
    "#         for i in range(left, right + 1):\n",
    "#             temp[i] = nums[i]\n",
    "\n",
    "#         i = left\n",
    "#         j = mid + 1\n",
    "#         res = 0\n",
    "#         for k in range(left, right + 1):\n",
    "#             if i > mid:\n",
    "#                 nums[k] = temp[j]\n",
    "#                 j += 1\n",
    "#             elif j > right:\n",
    "#                 nums[k] = temp[i]\n",
    "#                 i += 1\n",
    "#             elif temp[i] <= temp[j]:\n",
    "#                 # 此时前数组元素出列，不统计逆序对\n",
    "#                 nums[k] = temp[i]\n",
    "#                 i += 1\n",
    "#             else:\n",
    "#                 # assert temp[i] > temp[j]\n",
    "#                 # 此时后数组元素出列，统计逆序对，快就快在这里，一次可以统计出一个区间的个数的逆序对\n",
    "#                 nums[k] = temp[j]\n",
    "#                 j += 1\n",
    "#                 # 例：[7, 8, 9][4, 6, 9]，4 与 7 以及 7 后面所有的数都构成逆序对\n",
    "#                 res += (mid - i + 1)\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        tmp = sorted(set(record))\n",
    "        m = len(tmp)\n",
    "        for i in range(len(record)):\n",
    "            record[i] = 1 + bisect.bisect_left(tmp, record[i])\n",
    "        \n",
    "        tree = [0] * (m + 1)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(record):\n",
    "            cnt, t = 0, x\n",
    "            while t > 0:\n",
    "                cnt += tree[t]\n",
    "                t &= t - 1\n",
    "            \n",
    "            ans += i - cnt\n",
    "            while x <= m:\n",
    "                tree[x] += 1\n",
    "                x += x & -x\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        lowbit = lambda x:-x&x\n",
    "        class tree_array:\n",
    "            def __init__(self,n):\n",
    "                self.n = n\n",
    "                self.data = [0]*(n+1)\n",
    "                for i in range(1,n+1):\n",
    "                    self.data[i] = lowbit(i)\n",
    "            def add(self,index):\n",
    "                while index<=self.n:\n",
    "                    self.data[index] -= 1\n",
    "                    index += lowbit(index)\n",
    "            def left(self,index):\n",
    "                res = 0\n",
    "                while index>0:\n",
    "                    res += self.data[index]\n",
    "                    index -= lowbit(index)\n",
    "                return res\n",
    "        n = len(nums)\n",
    "        nums = sorted([i for i in range(n)],key=lambda x:nums[x])\n",
    "        cnt = [0]*n\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]] = i+1\n",
    "        nums = tree_array(n)\n",
    "        res = 0\n",
    "        for i in cnt:\n",
    "            nums.add(i)\n",
    "            res += nums.left(i-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x&-x\n",
    "\n",
    "class BIT:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.size = n\n",
    "        self.data = [0] * (n+1)\n",
    "    \n",
    "    def pre_sum(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.data[x]\n",
    "            x-=lowbit(x)\n",
    "        return res\n",
    "\n",
    "    def add_one(self, x):\n",
    "        while x < self.size:\n",
    "            self.data[x] += 1\n",
    "            x+=lowbit(x)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        # 离散化\n",
    "        tmp = sorted(set(nums))\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = bisect.bisect_left(tmp, nums[i])+1\n",
    "        bit = BIT(max(nums))\n",
    "        print(nums)\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            res += bit.pre_sum(nums[i]-1)\n",
    "            bit.add_one(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        t = BIT(len(nums) + 1)\n",
    "        b = sorted(set(nums))\n",
    "        ans = 0\n",
    "        def pos(b, x):\n",
    "            l, r = -1, len(b) - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if b[mid] < x: l = mid\n",
    "                else: r = mid - 1\n",
    "            return l\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            #print(x, pos(b, x))\n",
    "            ans += t.query(pos(b, x) + 1)\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums):\n",
    "        sortednums = list(set(nums))\n",
    "        sortednums.sort()\n",
    "        l = len(sortednums)\n",
    "        kvm = {sortednums[i-1]: i for i in range(1, l + 1)}\n",
    "        arrTree = BIT(l)\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            arrTree.add(kvm[nums[i]], 1)\n",
    "            ans += arrTree.query(kvm[nums[i]]-1)\n",
    "        return ans\n",
    "    \n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "    def add(self, i, v):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += v\n",
    "            i += i&-i\n",
    "    def query(self, i):\n",
    "        # 当前值已加\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= i&-i\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums):\n",
    "        def lowbit(x):\n",
    "            return x&(-x)\n",
    "        def update(x,d):\n",
    "            while x<n:\n",
    "                tree[x]+=d\n",
    "                x+=lowbit(x)\n",
    "        \n",
    "        def sum(x):\n",
    "            ans=0\n",
    "            while x:\n",
    "                ans+=tree[x]\n",
    "                x-=lowbit(x)\n",
    "            return ans\n",
    "        n=len(nums)\n",
    "        uni=sorted(set(nums))\n",
    "        rank={v:i+1 for i,v in enumerate(uni)}\n",
    "        tree=[0]*(n+1)\n",
    "\n",
    "        ans=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            k=rank[nums[i]]\n",
    "            ans+=sum(k-1)\n",
    "            update(k,1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def merge_soft(nums, l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "\n",
    "            m = l + (r-l)//2\n",
    "\n",
    "            merge_soft(nums,l, m)\n",
    "            merge_soft(nums,m+1, r)\n",
    "\n",
    "            merge(nums, l, m, r)\n",
    "\n",
    "        def merge(nums, l, m, r):\n",
    "            \n",
    "            L = copy.copy(nums[l:m+1])\n",
    "            R = copy.copy(nums[m+1:r+1])\n",
    "            \n",
    "            # i, j 分别为左右数组的索引, k是合并后数组的索引\n",
    "            \n",
    "            i, j, k = 0, 0, l\n",
    "            tmp = []\n",
    "            global res\n",
    "            while k <= r:\n",
    "                if i < len(L) and j < len(R):\n",
    "                    if L[i][0] <= R[j][0]:\n",
    "                        \n",
    "                        tmp.append(L[i])\n",
    "                        self.res += j\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        # nums[k] = R[j]\n",
    "                        tmp.append(R[j])\n",
    "                        \n",
    "                        j += 1\n",
    "                elif i < len(L):\n",
    "                    \n",
    "                    tmp.append(L[i])\n",
    "                    self.res += j\n",
    "                    i += 1\n",
    "\n",
    "                elif j < len(R):\n",
    "                    tmp.append(R[j])\n",
    "                    j += 1\n",
    "\n",
    "                k += 1\n",
    "                    \n",
    "            nums[l:r+1] = tmp\n",
    "\n",
    "\n",
    "        if nums == []:\n",
    "            return 0\n",
    "\n",
    "        n = len(nums)\n",
    "        self.res = 0\n",
    "        \n",
    "        nums = [(num,idx) for idx,num in enumerate(nums)]\n",
    "        # print(nums)\n",
    "        # print(self.res)\n",
    "        merge_soft(nums, 0, n-1)\n",
    "        # print(nums)\n",
    "        # print(self.res)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        root = [0] * (len(nums)+1)\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "        def update(index,val):\n",
    "            while index < len(root):\n",
    "                root[index] += val\n",
    "                index += lowbit(index)\n",
    "        def query(index):\n",
    "            res = 0\n",
    "            while index > 0:\n",
    "                res += root[index]\n",
    "                index -= lowbit(index)\n",
    "            return res\n",
    "        new_nums = sorted(list(set(nums)))\n",
    "        nums_map = { num:idx+1 for idx,num in enumerate(new_nums)}\n",
    "        res = 0\n",
    "        for num in nums[::-1]:\n",
    "            idx = nums_map[num]\n",
    "            res += query(idx-1)\n",
    "            update(idx,1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "\n",
    "        def mergeSort(left: int, right: int) -> None:\n",
    "            if left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                mergeSort(left, mid)\n",
    "                mergeSort(mid + 1, right)\n",
    "                merge(left, mid, right)\n",
    "        \n",
    "        def merge(left: int, mid: int, right: int) -> None:\n",
    "            nonlocal cnt\n",
    "            idx, idx1, idx2 = 0, left, mid + 1\n",
    "            temp = [0] * (right - left + 1)\n",
    "\n",
    "            while idx1 <= mid and idx2 <= right:\n",
    "                if nums[idx1] <= nums[idx2]:\n",
    "                    temp[idx] = nums[idx1]\n",
    "                    idx1 += 1\n",
    "                else:\n",
    "                    temp[idx] = nums[idx2]\n",
    "                    cnt += (mid - idx1 + 1)\n",
    "                    idx2 += 1\n",
    "                idx += 1\n",
    "            \n",
    "            while idx1 <= mid:\n",
    "                temp[idx] = nums[idx1]\n",
    "                idx += 1\n",
    "                idx1 += 1\n",
    "            \n",
    "            while idx2 <= right:\n",
    "                temp[idx] = nums[idx2]\n",
    "                idx += 1\n",
    "                idx2 += 1\n",
    "            for i in range(right - left + 1):\n",
    "                nums[left + i] = temp[i]\n",
    "        \n",
    "        mergeSort(0, len(nums) - 1)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Callable, Literal, Dict\n",
    "\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    def __init__(self, nums: List[int], build_tree: bool = True) -> None:\n",
    "        \"\"\"\n",
    "        build_tree: 如果已知nums是全0数组(这很常见), 可以令build_tree=False\n",
    "        \"\"\"\n",
    "        self.nums = nums\n",
    "        self.nums_len = len(nums)\n",
    "        self.tree = self.nums.copy()\n",
    "        if build_tree:\n",
    "            self._build_tree(nums)\n",
    "\n",
    "    @staticmethod\n",
    "    def _lowbit(idx: int) -> int:\n",
    "        return idx & -idx\n",
    "\n",
    "    def _build_tree(self, nums: List[int]) -> None:\n",
    "        for i in range(self.nums_len):\n",
    "            p = i + self._lowbit(i+1)\n",
    "            if p < self.nums_len:\n",
    "                self.tree[p] += self.tree[i]\n",
    "\n",
    "    def prefix_sum(self, hi: int) -> int:\n",
    "        \"\"\"sum(nums[..hi])\"\"\"\n",
    "        assert hi < self.nums_len\n",
    "        res = 0\n",
    "        while hi >= 0:\n",
    "            res += self.tree[hi]\n",
    "            hi -= self._lowbit(hi+1)\n",
    "        return res\n",
    "\n",
    "    def query_range(self, lo: int, hi: int) -> int:\n",
    "        \"\"\"sum(nums[lo..hi])\"\"\"\n",
    "        res = self.prefix_sum(hi)\n",
    "        if lo > 0:\n",
    "            res -= self.prefix_sum(lo - 1)\n",
    "        return res\n",
    "\n",
    "    def add(self, idx: int, val: int) -> None:\n",
    "        \"\"\"`add mode`\"\"\"\n",
    "        assert idx >= 0\n",
    "        while idx < self.nums_len:\n",
    "            self.tree[idx] += val\n",
    "            idx += self._lowbit(idx+1)\n",
    "\n",
    "\n",
    "def discretize(nums: List[int]) -> Dict[int, int]:\n",
    "    nums = sorted(nums)\n",
    "    unique(nums)\n",
    "    return {x: i for i, x in enumerate(nums)}\n",
    "\n",
    "\n",
    "def unique(nums: List[int]) -> None:\n",
    "    n = len(nums)\n",
    "    lo = 1  # 将被赋值, 但未被赋值. ignore 0\n",
    "    for hi in range(1, n):\n",
    "        if nums[hi] != nums[hi-1]:\n",
    "            nums[lo] = nums[hi]\n",
    "            lo += 1\n",
    "    # \n",
    "    for _ in range(lo, n):\n",
    "        nums.pop()\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        -: bit, add: 按nums的顺序添加, x0需要mapper->x, +=1\n",
    "            query: 查询比x大的count(倒着遍历, 比当前元素小的count)\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        mapper = discretize(nums)\n",
    "        n = len(mapper)\n",
    "        bit = BinaryIndexedTree([0] * n, False)\n",
    "        for x0 in reversed(nums):\n",
    "            x = mapper[x0]  # 0..n-1\n",
    "            if x-1 >= 0:\n",
    "                res += bit.prefix_sum(x-1)\n",
    "            bit.add(x, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(i, delta):      # 单点更新：执行+delta\n",
    "            while i<len(tree):\n",
    "                tree[i] += delta\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):           # 前缀和查询\n",
    "            presum = 0\n",
    "            while i>0:\n",
    "                presum += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return presum\n",
    "        \n",
    "        '''主程序'''\n",
    "        n = len(nums)\n",
    "\n",
    "        # 离散化：绝对数值转秩次【rank从1开始】\n",
    "        uniques = sorted(set(nums))\n",
    "        rank_map = {v:i+1 for i,v in enumerate(uniques)}\n",
    "        \n",
    "        # 构建树状数组\n",
    "        tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始\n",
    "\n",
    "        # 从右往左查询：nums[i:]中比nums[i]小的元素个数\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            rank = rank_map[nums[i]]    # 当前值的排名\n",
    "            ans += query(rank - 1)      # 查询排名比当前nums[i]还要小的元素的个数\n",
    "                                        # 【查询 rank-1，不包括自身】\n",
    "            add(rank, 1)                # 单点更新+1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# name:Aoobex\n",
    "from bisect import bisect_left\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums_index = []\n",
    "        for index, num in enumerate(nums):\n",
    "            nums_index.append([num, index])\n",
    "        nums_index = sorted(nums_index)\n",
    "        index_sorted = []\n",
    "        ans = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            insert_index = bisect_left(index_sorted, nums_index[i][1])\n",
    "            index = nums_index[i][1]\n",
    "            ans += n - index - 1 + insert_index - len(index_sorted)\n",
    "            index_sorted.insert(insert_index, nums_index[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0]*(n+1)\n",
    "        def lower_bit(x): return x&(-x)\n",
    "        def add(x, v):\n",
    "            while x <= n:\n",
    "                f[x] += v\n",
    "                x += lower_bit(x)\n",
    "        def sum(x):\n",
    "            res = 0\n",
    "            while x > 0:\n",
    "                res += f[x]\n",
    "                x -= lower_bit(x)\n",
    "            return res\n",
    "\n",
    "        data = sorted(zip(nums, range(1, n+1)))\n",
    "        ans = 0\n",
    "        for _, x in data[::-1]:\n",
    "            add(x, 1)\n",
    "            ans += sum(x-1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeList:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "\n",
    "    def lowBit(self,index):\n",
    "        index = index & -index\n",
    "        return index\n",
    "\n",
    "    def update(self,index,num):\n",
    "        while index<len(self.tree):\n",
    "            self.tree[index] += num\n",
    "            index += self.lowBit(index)\n",
    "\n",
    "    def count(self,index):\n",
    "        res = 0\n",
    "        while index>0:\n",
    "            res += self.tree[index]\n",
    "            index -= self.lowBit(index)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        numSet = sorted(set(nums))\n",
    "        rank_map = {v:i+1 for i,v in enumerate(numSet)}\n",
    "        res = [0] * len(nums)\n",
    "        tree = TreeList(len(numSet) + 1)\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            index = rank_map[nums[i]]\n",
    "            res[i] += tree.count(index-1)\n",
    "            tree.update(index,1)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        disc = list(sorted(set(nums)))\n",
    "        id_map = {}\n",
    "        for x in disc:\n",
    "            id_map[x] = bisect_left(disc, x) + 1\n",
    "\n",
    "        n = len(disc)\n",
    "        disc = None\n",
    "        tree = [0] * (n + 1)\n",
    "\n",
    "        def query(x: int) -> int:\n",
    "            res = 0\n",
    "            while x > 0:\n",
    "                res += tree[x]\n",
    "                x -= x & (-x)\n",
    "            return res\n",
    "\n",
    "        def update(x: int) -> None:\n",
    "            while x <= n:\n",
    "                tree[x] += 1\n",
    "                x += x & (-x)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            id = id_map[nums[i]]\n",
    "            ans += query(id - 1)\n",
    "            update(id)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        arr = sorted(enumerate(nums), key = lambda x: x[1])\n",
    "        i = 1\n",
    "\n",
    "        for x, y in arr:\n",
    "            nums[x] = i\n",
    "            i += 1\n",
    "        tree = [0] * (i + 1)\n",
    "        n = len(nums)\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "        def update(x):\n",
    "            while x <= i:\n",
    "                tree[x] += 1\n",
    "                x += lowbit(x)\n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x > 0:\n",
    "                ans += tree[x]\n",
    "                x -= lowbit(x)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        # print(nums)\n",
    "        r = 0\n",
    "        for j in range(n-1, -1, -1):\n",
    "            r += query(nums[j])\n",
    "            update(nums[j])\n",
    "\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    tmp = [0]*500001\n",
    "    res = 0\n",
    "    def merge(self,record: List[int],l: int,mid: int,r: int):\n",
    "        idx = 0\n",
    "        a,b = l,mid+1\n",
    "        while a<=mid and b<=r:\n",
    "            if record[a] > record[b]:\n",
    "                self.res += r-b+1\n",
    "                self.tmp[idx] = record[a]\n",
    "                idx+=1\n",
    "                a+=1\n",
    "            else:\n",
    "                self.tmp[idx] = record[b]\n",
    "                idx+=1\n",
    "                b+=1\n",
    "        \n",
    "        while a<=mid:\n",
    "            self.tmp[idx] = record[a]\n",
    "            idx+=1\n",
    "            a+=1\n",
    "\n",
    "        while b<=r:\n",
    "            self.tmp[idx] = record[b]\n",
    "            idx+=1\n",
    "            b+=1\n",
    "        \n",
    "        idx = 0\n",
    "        for i in range(l,r+1):\n",
    "            record[i] = self.tmp[idx]\n",
    "            idx+=1\n",
    "    def dfs(self,record: List[int],l: int,r: int):\n",
    "        n = r-l+1\n",
    "        if n<2:return\n",
    "        \n",
    "        mid = (r+l)//2\n",
    "        self.dfs(record,l,mid)\n",
    "        self.dfs(record,mid+1,r)\n",
    "\n",
    "        self.merge(record,l,mid,r)\n",
    "\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        n = len(record)\n",
    "        if n<2:return 0\n",
    "        self.dfs(record,0,n-1)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def count(l, r):\n",
    "            if r-l < 2:\n",
    "                return 0\n",
    "            m = (l+r)//2\n",
    "            p = count(l, m)+count(m, r)\n",
    "            n1 = nums[l:m]\n",
    "            n2 = nums[m:r]\n",
    "            n1.sort()\n",
    "            n2.sort()\n",
    "            for i in range(m-l):\n",
    "                p += bisect.bisect_left(n2, n1[i])\n",
    "            return p\n",
    "        return count(0, len(nums))\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        n=len(nums)\n",
    "        if n<=1:return 0\n",
    "        # d=defaultdict(int)\n",
    "        # for e in nums:d[e]+=1\n",
    "        # temp=[(k,v) for (k,v) in d.items()]\n",
    "        # temp.sort(key=lambda x:x[0])\n",
    "        # d2=defaultdict(int)\n",
    "        # pre=0\n",
    "        # for k,v in temp:\n",
    "        #     d2[k]=pre\n",
    "        #     pre+=v\n",
    "\n",
    "        temp=copy.deepcopy(nums)\n",
    "        temp.sort()\n",
    "        d2=defaultdict(int)\n",
    "        flag=None\n",
    "        for i,num in enumerate(temp):\n",
    "            if nums!=flag:\n",
    "                flag=num\n",
    "                d2[num]=i\n",
    "\n",
    "\n",
    "        bit=[0]*(n+1)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            e=d2[nums[i]]+1\n",
    "            pos=e\n",
    "            while pos:\n",
    "                res+=bit[pos]\n",
    "                pos-=(pos&-pos)\n",
    "            pos=e\n",
    "            while pos<n+1:\n",
    "                bit[pos]+=1\n",
    "                pos+=(pos&-pos)\n",
    "        return n*(n-1)//2 - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        if not record:\n",
    "            return 0\n",
    "        \n",
    "        mp = {}\n",
    "        for i, x in enumerate(sorted(record), start=1):\n",
    "            mp[x] = i\n",
    "\n",
    "        n = i\n",
    "        bit = Bit(n)\n",
    "        ans = 0\n",
    "        for index, i in enumerate(record):\n",
    "            #print(index, bit.prefixSum(i))\n",
    "            i = mp[i]\n",
    "            ans += index - bit.prefixSum(i)\n",
    "            bit.add(i, 1)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += v\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def prefixSum(self, i):\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    __slots__ = 'size', 'tree'\n",
    "\n",
    "    def __init__(self, n: List[int]):\n",
    "        self.size = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "\n",
    "    def update(self, index: int, delta: int) -> None:\n",
    "        i = index\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += delta\n",
    "            i += i & -i \n",
    "\n",
    "\n",
    "    def query(self, i):\n",
    "        s = 0\n",
    "        while i:\n",
    "            s += self.tree[i]\n",
    "            i &= i - 1\n",
    "        return s \n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2: return 0\n",
    "        s = list(set(nums))\n",
    "        m = len(s)\n",
    "\n",
    "        heapify(s)\n",
    "        rank_map = Counter()\n",
    "        cnt = 1\n",
    "        for _ in range(m):\n",
    "            x = heappop(s)\n",
    "            rank_map[x] = cnt\n",
    "            cnt += 1\n",
    "        \n",
    "        ans = 0\n",
    "        t = Tree(m)\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            rank = rank_map[nums[i]]\n",
    "            t.update(rank, 1)\n",
    "            ans += t.query(rank - 1)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "    def __init__(self,n):\n",
    "        self.tree=[0]*(n+1)\n",
    "\n",
    "    def update(self,i):\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i]+=1\n",
    "            i+=i&(-i)\n",
    "\n",
    "    def query(self,i):\n",
    "        ans=0\n",
    "        while i>0:\n",
    "            ans+=self.tree[i]\n",
    "            i&=i-1\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        r=sorted(list(set(record)),reverse=True)\n",
    "        d=dict(zip(r,range(1,len(r)+1)))\n",
    "        fw=Fenwick(len(r))\n",
    "        ans=0\n",
    "        for rcd in record:\n",
    "            fw.update(d[rcd])\n",
    "            ans+=fw.query(d[rcd]-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.arr = [0]*(n+1)\n",
    "        self.n = n\n",
    "    def update(self,k,val):\n",
    "        while k<=self.n:\n",
    "            self.arr[k] += val\n",
    "            k += (k&(-k))\n",
    "    def getsum(self,k):\n",
    "        res = 0\n",
    "        while k>0:\n",
    "            res += self.arr[k]\n",
    "            k -= (k&(-k))\n",
    "        return res\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        nums = record\n",
    "        # if len(nums)<=1:\n",
    "        #     return 0\n",
    "        # temp = nums[:]\n",
    "        # def mergesort(nums,l,r,temp):\n",
    "        #     if l==r:\n",
    "        #         return 0\n",
    "        #     mid = (l + r)//2\n",
    "        #     res = 0\n",
    "        #     res = res + mergesort(nums,l,mid,temp)\n",
    "        #     res = res + mergesort(nums,mid+1,r,temp)\n",
    "        #     if nums[mid]<nums[mid+1]:\n",
    "        #         return res\n",
    "        #     for i in range(l,r+1):\n",
    "        #         temp[i] = nums[i]\n",
    "        #     cl = l\n",
    "        #     cr = mid+1\n",
    "        #     for i in range(l,r+1):\n",
    "        #         if cl>mid:\n",
    "        #             nums[i] = temp[cr]\n",
    "        #             cr = cr + 1\n",
    "        #         elif cr>r:\n",
    "        #             nums[i] = temp[cl]\n",
    "        #             cl = cl + 1\n",
    "        #         else:\n",
    "        #             if temp[cl]<=temp[cr]:\n",
    "        #                 nums[i] = temp[cl]\n",
    "        #                 cl = cl + 1\n",
    "        #             else:\n",
    "        #                 nums[i] = temp[cr]\n",
    "        #                 res = res + mid+1-cl\n",
    "        #                 cr = cr + 1\n",
    "        #     return res \n",
    "        # return mergesort(nums,0,len(nums)-1,temp)\n",
    "        n = len(nums)\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        d = list(set(nums))\n",
    "        d.sort()\n",
    "        dic = {}\n",
    "        for i in range(len(d)):\n",
    "            dic[d[i]] = i+1\n",
    "        bit = BIT(n)\n",
    "        res = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            idx = dic[nums[i]]\n",
    "            res += bit.getsum(idx-1)\n",
    "            bit.update(idx,1)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        class BitIndexedTree:\n",
    "            def __init__(self, size: int):\n",
    "                self.size = size\n",
    "                self.tree = [0 for _ in range(size+1)]\n",
    "            \n",
    "            def _lowbit(self, index):\n",
    "                return index & (-index)\n",
    "            \n",
    "            def update(self, index, value):\n",
    "                while index <= self.size:\n",
    "                    self.tree[index] += value\n",
    "                    index += self._lowbit(index)\n",
    "            \n",
    "            def query(self, index):\n",
    "                res = 0\n",
    "                while index > 0:\n",
    "                    res += self.tree[index]\n",
    "                    index -= self._lowbit(index)\n",
    "                return res\n",
    "\n",
    "        s = sorted(list(set(nums)))\n",
    "        rank = {}\n",
    "        for x in s:\n",
    "            rank[x] = len(rank) + 1\n",
    "        \n",
    "        res = 0\n",
    "        tree = BitIndexedTree(len(rank))\n",
    "\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            r = rank[nums[i]]\n",
    "            tree.update(r, 1)\n",
    "            res += tree.query(r-1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class BIT:\n",
    "    def lowbit(self,x)->int:\n",
    "        return x&(-x)\n",
    "    def __init__(self,n):\n",
    "        self.tree=[0]*(n+1)\n",
    "    def update(self,index,val)->int:\n",
    "        while index<=len(self.tree)-1:\n",
    "            self.tree[index]+=val\n",
    "            index+=self.lowbit(index)\n",
    "    def getsum(self,x)->int:\n",
    "        ans=0\n",
    "        while x>0:\n",
    "            ans+=self.tree[x]\n",
    "            x-=self.lowbit(x)\n",
    "        return ans\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        bt=BIT(len(nums))\n",
    "        lisan=sorted(set(nums))\n",
    "        dic={x:i+1 for i,x in enumerate(lisan)}\n",
    "        dic=[dic[x] for x in nums]\n",
    "        ans=0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            ans+=bt.getsum(dic[i]-1)\n",
    "            bt.update(dic[i],1)\n",
    "        return ans\n",
    "s=Solution()\n",
    "print(s.reversePairs([7, 5, 6, 4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:  \n",
    "        n = len(nums)\n",
    "        dic = {}\n",
    "        nums1 = sorted(nums)\n",
    "        for i,x in enumerate(nums1):\n",
    "            dic[x] = i + 1\n",
    "        for i in range(n):\n",
    "            nums[i] = dic[nums[i]]\n",
    "        # print(nums)\n",
    "        lst  = [0] * (n + 1)\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        def query(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans += lst[x]\n",
    "                x -= lowbit(x)\n",
    "            return ans\n",
    "        def update(x):\n",
    "            while x <= n:\n",
    "                lst[x] += 1\n",
    "                x += lowbit(x)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            ans += query(nums[i] - 1)\n",
    "            update(nums[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        class FenwickTree:\n",
    "            def __init__(self, n):\n",
    "                self.size = n\n",
    "                self.tree = [0 for _ in range(n + 1)]\n",
    "\n",
    "            def __lowbit(self, index):\n",
    "                return index & (-index)\n",
    "\n",
    "            # 单点更新：从下到上，最多到 len，可以取等\n",
    "            def update(self, index, delta):\n",
    "                while index <= self.size:\n",
    "                    self.tree[index] += delta\n",
    "                    index += self.__lowbit(index)\n",
    "\n",
    "            # 区间查询：从上到下，最少到 1，可以取等\n",
    "            def query(self, index):\n",
    "                res = 0\n",
    "                while index > 0:\n",
    "                    res += self.tree[index]\n",
    "                    index -= self.__lowbit(index)\n",
    "                return res\n",
    "\n",
    "        # 特判\n",
    "        size = len(nums)\n",
    "        if size < 2:\n",
    "            return 0\n",
    "\n",
    "        # 原始数组去除重复以后从小到大排序，这一步叫做离散化\n",
    "        s = list(set(nums))\n",
    "\n",
    "        # 构建最小堆，因为从小到大一个一个拿出来，用堆比较合适\n",
    "        import heapq\n",
    "        heapq.heapify(s)\n",
    "\n",
    "        # 由数字查排名\n",
    "        rank_map = dict()\n",
    "        rank = 1\n",
    "        # 不重复数字的个数\n",
    "        rank_map_size = len(s)\n",
    "        for _ in range(rank_map_size):\n",
    "            num = heapq.heappop(s)\n",
    "            rank_map[num] = rank\n",
    "            rank += 1\n",
    "\n",
    "        res = 0\n",
    "        # 树状数组只要不重复数字个数这么多空间就够了\n",
    "        ft = FenwickTree(rank_map_size)\n",
    "\n",
    "        # 从后向前看，拿出一个数字来，就更新一下，然后向前查询比它小的个数\n",
    "        for i in range(size - 1, -1, -1):\n",
    "            rank = rank_map[nums[i]]\n",
    "            ft.update(rank, 1)\n",
    "            res += ft.query(rank - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        class FenwickTree:\n",
    "            def __init__(self, n):\n",
    "                self.size = n\n",
    "                self.tree = [0 for _ in range(n + 1)]\n",
    "\n",
    "            def __lowbit(self, index):\n",
    "                return index & (-index)\n",
    "\n",
    "            # 单点更新：从下到上，最多到 len，可以取等\n",
    "            def update(self, index, delta):\n",
    "                while index <= self.size:\n",
    "                    self.tree[index] += delta\n",
    "                    index += self.__lowbit(index)\n",
    "\n",
    "            # 区间查询：从上到下，最少到 1，可以取等\n",
    "            def query(self, index):\n",
    "                res = 0\n",
    "                while index > 0:\n",
    "                    res += self.tree[index]\n",
    "                    index -= self.__lowbit(index)\n",
    "                return res\n",
    "\n",
    "        # 特判\n",
    "        size = len(nums)\n",
    "        if size < 2:\n",
    "            return 0\n",
    "\n",
    "        # 原始数组去除重复以后从小到大排序，这一步叫做离散化\n",
    "        s = list(set(nums))\n",
    "\n",
    "        # 构建最小堆，因为从小到大一个一个拿出来，用堆比较合适\n",
    "        import heapq\n",
    "        heapq.heapify(s)\n",
    "\n",
    "        # 由数字查排名\n",
    "        rank_map = dict()\n",
    "        rank = 1\n",
    "        # 不重复数字的个数\n",
    "        rank_map_size = len(s)\n",
    "        for _ in range(rank_map_size):\n",
    "            num = heapq.heappop(s)\n",
    "            rank_map[num] = rank\n",
    "            rank += 1\n",
    "\n",
    "        res = 0\n",
    "        # 树状数组只要不重复数字个数这么多空间就够了\n",
    "        ft = FenwickTree(rank_map_size)\n",
    "\n",
    "        # 从后向前看，拿出一个数字来，就更新一下，然后向前查询比它小的个数\n",
    "        for i in range(size - 1, -1, -1):\n",
    "            rank = rank_map[nums[i]]\n",
    "            ft.update(rank, 1)\n",
    "            res += ft.query(rank - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def mSort(tmp, l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            mid = (l + r) // 2\n",
    "            inv_count = mSort(tmp, l, mid) + mSort(tmp, mid + 1, r)\n",
    "            i, j, pos = l, mid + 1, l\n",
    "            while i <= mid and j <= r:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp[pos] = nums[i]\n",
    "                    i += 1\n",
    "                    inv_count += (j - (mid + 1))\n",
    "                else:\n",
    "                    tmp[pos] = nums[j]\n",
    "                    j += 1\n",
    "                pos += 1\n",
    "            for k in range(i, mid + 1):\n",
    "                tmp[pos] = nums[k]\n",
    "                inv_count += (j - (mid + 1))\n",
    "                pos += 1\n",
    "            for k in range(j, r + 1):\n",
    "                tmp[pos] = nums[k]\n",
    "                pos += 1\n",
    "            nums[l:r+1] = tmp[l:r+1]\n",
    "            return inv_count\n",
    "\n",
    "        n = len(nums)\n",
    "        tmp = [0] * n\n",
    "        return mSort(tmp, 0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        class FenwickTree:\n",
    "            def __init__(self, n):\n",
    "                self.size = n\n",
    "                self.tree = [0 for _ in range(n+1)]\n",
    "            \n",
    "            def __lowbit(self, index):\n",
    "                return index & (-index)\n",
    "            \n",
    "            def update(self, index, delta):\n",
    "                while index <= self.size:\n",
    "                    self.tree[index] += delta\n",
    "                    index += self.__lowbit(index)\n",
    "            \n",
    "            def query(self, index):\n",
    "                res = 0\n",
    "                while index > 0:\n",
    "                    res += self.tree[index]\n",
    "                    index -= self.__lowbit(index)\n",
    "                return res\n",
    "        \n",
    "        heap = list(set(nums))\n",
    "        if len(heap) < 2:\n",
    "            return 0\n",
    "        n = len(heap)\n",
    "        tree_arr = FenwickTree(n)\n",
    "        import heapq\n",
    "        heapq.heapify(heap)\n",
    "        rank = 1\n",
    "        nums2rank = {}\n",
    "        while heap:\n",
    "            num = heapq.heappop(heap)\n",
    "            nums2rank[num] = rank\n",
    "            rank += 1\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            res += tree_arr.query(nums2rank[nums[i]] - 1)\n",
    "            tree_arr.update(nums2rank[nums[i]], 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        def recur(i, j):\n",
    "            if j == i:\n",
    "                return [nums[i]]\n",
    "            if j == i + 1:\n",
    "                if nums[i] > nums[j]:\n",
    "                    self.res += 1\n",
    "                    return [nums[j], nums[i]]\n",
    "                else:\n",
    "                    return [nums[i], nums[j]]\n",
    "            m = (i + j) // 2\n",
    "            left_list = recur(i, m)\n",
    "            right_list = recur(m + 1, j)\n",
    "            a, b = 0, 0\n",
    "            tmp =[]\n",
    "            while a < len(left_list) or b < len(right_list):\n",
    "                if a == len(left_list):\n",
    "                    tmp.append(right_list[b])\n",
    "                    b += 1\n",
    "                elif b == len(right_list):\n",
    "                    tmp.append(left_list[a])\n",
    "                    a += 1\n",
    "                elif left_list[a] > right_list[b]:\n",
    "                    self.res += len(left_list) - a\n",
    "                    tmp.append(right_list[b])\n",
    "                    b += 1\n",
    "                else:\n",
    "                    tmp.append(left_list[a])\n",
    "                    a += 1\n",
    "            return tmp\n",
    "\n",
    "        recur(0, len(nums) - 1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        # 思路：归并排序\n",
    "        # 假设 归并排序函数 merge_sort 已经能够找到区间 （L, R）内的逆序对数量\n",
    "        # 那么 左半段逆序对数量为 merge_sort(L, mid)\n",
    "        # 右半段逆序对数量为 merge_sort(mid_+1, R)\n",
    "        # 最难求的是跨左右两端的逆序对数量\n",
    "        # 假设现在要求右半段 nums[j] 在与左半段能够构成逆序对的数量\n",
    "        # 现在在归并是，左半段nums[i] > nums[j]， 那么左半段i后面的数都大于nums[j]\n",
    "        # 都能构成逆序对，因此，左半段与nums[j] 构成逆序对的数量是 mid - i + 1\n",
    "\n",
    "        def merge_sort(l, r):\n",
    "            if l >= r: return 0\n",
    "            mid = l + r >> 1\n",
    "            res = merge_sort(l, mid) + merge_sort(mid+1, r)\n",
    "\n",
    "            # 归并过程\n",
    "            tmp = []\n",
    "            i = l\n",
    "            j = mid + 1\n",
    "            while i <= mid and j <= r:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp.append(nums[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res += mid - i + 1  # 每次移动j时，都要计算一下nums[j]的左半段逆序对\n",
    "                    tmp.append(nums[j])\n",
    "                    j += 1\n",
    "            while i <= mid:\n",
    "                tmp.append(nums[i])\n",
    "                i += 1\n",
    "            while j <= r:\n",
    "                tmp.append(nums[j])\n",
    "                j += 1\n",
    "            for i in range(len(tmp)):\n",
    "                nums[l+i] = tmp[i]\n",
    "            return res\n",
    "        \n",
    "        return merge_sort(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        self.count = 0\n",
    "\n",
    "        def _mergesort(start, end):\n",
    "            if start>=end:\n",
    "                return\n",
    "            mid = (start+end)//2\n",
    "            _mergesort(start,mid)\n",
    "            _mergesort(mid+1,end)\n",
    "\n",
    "            p1=start\n",
    "            p2=mid+1\n",
    "            temp = []\n",
    "            while p1<=mid and p2<=end:\n",
    "                if record[p1]<=record[p2]:\n",
    "                    temp.append(record[p1])\n",
    "                    p1+=1\n",
    "                else:\n",
    "                    self.count +=mid-p1+1\n",
    "                    temp.append(record[p2])\n",
    "                    p2+=1\n",
    "            while p1<=mid:\n",
    "                temp.append(record[p1])\n",
    "                p1+=1\n",
    "            while p2<=end:\n",
    "                temp.append(record[p2])\n",
    "                p2+=1\n",
    "            for i in range(len(temp)):\n",
    "                record[start+i] = temp[i]\n",
    "        _mergesort(0,len(record)-1)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        n = len(record)\n",
    "        tmp = record[::]\n",
    "\n",
    "        def countCross(record, left, right, mid):\n",
    "            res = 0\n",
    "            for i in range(left, right+1):\n",
    "                tmp[i] = record[i]\n",
    "            i = left\n",
    "            j = mid + 1\n",
    "            for k in range(left, right+1):\n",
    "                if i > mid:\n",
    "                    record[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j > right:\n",
    "                    record[k] = tmp[i]\n",
    "                    i += 1\n",
    "                elif tmp[i] <= tmp[j]:\n",
    "                    record[k] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    record[k] = tmp[j]\n",
    "                    res += mid - i + 1\n",
    "                    j += 1\n",
    "            return res\n",
    "\n",
    "        \n",
    "        def helper(record, left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            mid = (left+right)//2\n",
    "            l = helper(record, left, mid)\n",
    "            r = helper(record, mid+1, right)\n",
    "            if record[mid+1] > record[mid]:\n",
    "                return l + r \n",
    "            c = countCross(record, left, right, mid)\n",
    "            return l + r + c\n",
    "        return helper(record, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:  \n",
    "        n = len(nums)\n",
    "        def merge(lst,l,r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            mid = l + r >> 1\n",
    "            ans = merge(lst,l,mid) + merge(lst,mid + 1,r)\n",
    "            i,j = l,mid + 1\n",
    "            k = 0\n",
    "            tmp = [0] * (r - l + 1)\n",
    "            while i <= mid and j <= r:\n",
    "                if nums[i] > nums[j]:\n",
    "                    ans += (mid - i + 1)\n",
    "                    tmp[k] = nums[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    tmp[k] = nums[i]\n",
    "                    i += 1\n",
    "                k += 1\n",
    "            while i <= mid:\n",
    "                tmp[k] = nums[i]\n",
    "                k += 1\n",
    "                i += 1\n",
    "            while j <= r:\n",
    "                tmp[k] = nums[j]\n",
    "                k += 1\n",
    "                j += 1\n",
    "            i = l\n",
    "            for x in tmp:\n",
    "                nums[l] = x\n",
    "                l += 1\n",
    "            return ans\n",
    "        return merge(nums,0,n - 1)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        n=len(record)\n",
    "        left=0\n",
    "        def process(left,right):\n",
    "            if left>=right:\n",
    "                return 0\n",
    "            mid=(left+right)//2\n",
    "            return process(left,mid)+process(mid+1,right)+merge(left,right,mid)\n",
    "        \n",
    "        def merge(left,right,mid):\n",
    "            \n",
    "            orileft=left\n",
    "            sum=0\n",
    "            k=mid+1\n",
    "            stock=[]\n",
    "            while left<=mid and k<=right:\n",
    "                if record[left]>record[k]:\n",
    "                    sum+=mid-left+1\n",
    "                    stock.append(record[k])\n",
    "                    k+=1\n",
    "                else:\n",
    "                    stock.append(record[left])\n",
    "                    left+=1\n",
    "            while left<=mid:\n",
    "                stock.append(record[left])\n",
    "                left+=1\n",
    "            while k<=right:\n",
    "                stock.append(record[k])\n",
    "                k+=1\n",
    "            record[orileft:right+1]=stock\n",
    "            return sum\n",
    "        return process(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def merge_sort(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            mid = (l + r) // 2\n",
    "            res = merge_sort(l, mid) + merge_sort(mid + 1, r)\n",
    "            i, j = l, mid + 1\n",
    "            tmp = []\n",
    "            while i <= mid or j <= r:\n",
    "                if i > mid:\n",
    "                    tmp.append(record[j])\n",
    "                    j += 1\n",
    "                elif j <= r and record[i] > record[j]:\n",
    "                    tmp.append(record[j])\n",
    "                    j += 1\n",
    "                    res += mid - i + 1\n",
    "                else:\n",
    "                    tmp.append(record[i])\n",
    "                    i += 1\n",
    "            record[l : r + 1] = tmp\n",
    "            return res\n",
    "        return merge_sort(0, len(record) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        if len(record) <= 1:\n",
    "            return 0\n",
    "        self.count = 0\n",
    "        def merge_sort(start, end):\n",
    "            if start == end:\n",
    "                return\n",
    "            else:\n",
    "                mid = (end + start) // 2\n",
    "                merge_sort(start, mid)\n",
    "                merge_sort(mid + 1, end)\n",
    "                left, right = start, mid + 1\n",
    "                res = []\n",
    "                while left <= mid or right <= end:\n",
    "                    if left > mid or (right <= end and record[left] > record[right]):\n",
    "                        res.append(record[right])\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        res.append(record[left])\n",
    "                        left += 1\n",
    "                        self.count += right - mid - 1\n",
    "                record[start:end+1] = res\n",
    "        merge_sort(0, len(record) - 1)\n",
    "        return self.count\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        def mergeSort(left, right):\n",
    "            if left >= right: return\n",
    "\n",
    "            mid = left + (right-left)//2\n",
    "\n",
    "            mergeSort(left, mid)\n",
    "            mergeSort(mid+1, right)\n",
    "            merge(left, mid, right)            \n",
    "        \n",
    "        def merge(left, mid, right):\n",
    "            nonlocal cnt\n",
    "            tmp = []\n",
    "\n",
    "            i = left\n",
    "            j = mid+1\n",
    "\n",
    "            while i <= mid and j <= right:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    tmp.append(nums[i])\n",
    "                    i+=1\n",
    "                else:\n",
    "                    tmp.append(nums[j])\n",
    "                    j+=1\n",
    "                    cnt+= (mid-i+1)\n",
    "            \n",
    "            while i <= mid:\n",
    "                tmp.append(nums[i])\n",
    "                i+=1\n",
    "            while j <= right:\n",
    "                tmp.append(nums[j])\n",
    "                j+=1\n",
    "            \n",
    "            nums[left:right+1] = tmp[:]\n",
    "\n",
    "\n",
    "        mergeSort(0, len(nums)-1)\n",
    "        return cnt\n",
    "        \n",
    "\n",
    "                 \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        \n",
    "        def count(nums1,nums2):\n",
    "            n1,n2 = len(nums1), len(nums2)\n",
    "            i,j = 0, 0\n",
    "            tmp = []\n",
    "            while i < n1 and j < n2:\n",
    "                if nums1[i] > nums2[j]:\n",
    "                    self.res += n1 - i\n",
    "                    tmp.append(nums2[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    tmp.append(nums1[i])\n",
    "                    i += 1\n",
    "\n",
    "            if i < n1:\n",
    "                tmp += nums1[i:]\n",
    "\n",
    "            if j < n2:\n",
    "                tmp += nums2[j:]\n",
    "\n",
    "            return tmp\n",
    "        \n",
    "        def merge(l,r):\n",
    "            if l == r:\n",
    "                return [record[l]]\n",
    "            if l > r:\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            left = merge(l,mid)\n",
    "            right = merge(mid+1,r)\n",
    "            return count(left,right)\n",
    "        \n",
    "        merge(0,len(record)-1)\n",
    "        return self.res\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def msort(l, r):\n",
    "            if l == r: return [record[l]]\n",
    "            if r - l == 1:\n",
    "                lv, rv = record[l], record[r]\n",
    "                if rv < lv:\n",
    "                    ret[-1] += 1\n",
    "                return [min(lv, rv), max(lv, rv)]\n",
    "\n",
    "            m = l + (r-l)//2\n",
    "            l1 = msort(l, m)\n",
    "            l2 = msort(m+1, r)\n",
    "            return merge(l1, l2)\n",
    "\n",
    "        def merge(l1, l2):\n",
    "            p1, p2 = 0, 0\n",
    "            n, m = len(l1), len(l2)\n",
    "            res = []\n",
    "            while p1 < n and p2 < m:\n",
    "                if l1[p1] > l2[p2]:\n",
    "                    res.append(l2[p2])\n",
    "                    p2 += 1\n",
    "                else:\n",
    "                    res.append(l1[p1])\n",
    "                    ret[-1] += p2\n",
    "                    p1 += 1\n",
    "            while p1 < n:\n",
    "                res.append(l1[p1])\n",
    "                ret[-1] += p2\n",
    "                p1 += 1\n",
    "            while p2 < m:\n",
    "                res.append(l2[p2])\n",
    "                p2 += 1\n",
    "            return res\n",
    "\n",
    "        ret = [0]\n",
    "        if not record:\n",
    "            return 0\n",
    "        msort(0, len(record)-1)\n",
    "        return ret[-1]\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def reverse(l,r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            mid = (l +r)//2\n",
    "            ret = reverse(l,mid) + reverse(mid+1,r)\n",
    "            b_l,b_r = l,mid+1\n",
    "            tmp = []\n",
    "            while b_l <= mid and b_r <= r:\n",
    "                if record[b_l] > record[b_r]:\n",
    "                    ret += mid-b_l+1\n",
    "                    tmp.append(record[b_r])\n",
    "                    b_r += 1\n",
    "                else:\n",
    "                    tmp.append(record[b_l])\n",
    "                    b_l += 1\n",
    "            if b_l <=mid:\n",
    "                tmp.extend([record[b] for b in range(b_l,mid+1)])\n",
    "            if b_r <= r:\n",
    "                tmp.extend([record[b] for b in range(b_r,r+1)])\n",
    "            record[l:r+1] = tmp\n",
    "            return ret\n",
    "        return reverse(0,len(record)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        self.ans=0\n",
    "        if not len(record):\n",
    "            return self.ans\n",
    "        def guibingsort(l,r):\n",
    "            # print(l,r)\n",
    "            if l==r:\n",
    "                return \n",
    "            mid=(l+r)//2\n",
    "            # print(l,mid,r)\n",
    "            guibingsort(l,mid)\n",
    "            guibingsort(mid+1,r)\n",
    "            l1,l2=l,mid+1\n",
    "            new_l=[]\n",
    "            # print(l,mid,r,record)\n",
    "\n",
    "            while l1<=mid and l2<=r:\n",
    "                # print(l,mid,r,l1,l2)\n",
    "                if record[l1]<=record[l2]:\n",
    "                    # print('a',record,l,mid,r,l1,l2,l2-mid-1,self.ans)\n",
    "\n",
    "                    new_l.append(record[l1])\n",
    "                    self.ans+=l2-mid-1\n",
    "\n",
    "                    l1+=1\n",
    "                else:\n",
    "                    # print(record,l,mid,r,l1,l2,l2-mid)\n",
    "                    new_l.append(record[l2])\n",
    "                    # self.ans+=l2-mid\n",
    "                    l2+=1\n",
    "            # if nums\n",
    "            if l1<=mid:\n",
    "                self.ans+=(l2-mid-1)*(mid-l1+1)\n",
    "                # l1+=1\n",
    "                new_l.extend(record[l1:mid+1])\n",
    "            if l2<=r:\n",
    "                new_l.extend(record[l2:r+1])\n",
    "\n",
    "            record[l:r+1]=new_l\n",
    "        \n",
    "            # return new_l\n",
    "        guibingsort(0,len(record)-1)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        \n",
    "        n = len(record)\n",
    "        nums = record\n",
    "        if not record:\n",
    "            return 0\n",
    "        def count(i, j):\n",
    "            if i == j:\n",
    "                return (0, [nums[i]])\n",
    "\n",
    "            m = i + (j - i) // 2\n",
    "            l, p1 = count(i, m)\n",
    "            r, p2 = count(m + 1, j)\n",
    "\n",
    "            ans = l + r\n",
    "            p = []\n",
    "            n1 = len(p1)\n",
    "            n2 = len(p2)\n",
    "            ii = jj = 0\n",
    "            while ii < n1 and jj < n2:\n",
    "                if p2[jj] < p1[ii]:\n",
    "                    ans += n1 - ii\n",
    "                    p.append(p2[jj])\n",
    "                    jj += 1\n",
    "                else:\n",
    "                    p.append(p1[ii])\n",
    "                    ii += 1\n",
    "\n",
    "            while ii < n1:\n",
    "                p.append(p1[ii])\n",
    "                ii += 1\n",
    "\n",
    "            while jj < n2:\n",
    "                p.append(p2[jj])\n",
    "                jj += 1\n",
    "\n",
    "            return (ans, p)\n",
    "\n",
    "        temp = count(0, n-1)\n",
    "        #print(temp)\n",
    "        return count(0, n-1)[0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        record_new = record.copy()\n",
    "        def reverse(l,r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            mid = (l +r)//2\n",
    "            \n",
    "            ret = reverse(l,mid) + reverse(mid+1,r)\n",
    "            b_l,b_r = l,mid+1\n",
    "            tmp = []\n",
    "            while b_l <= mid and b_r <= r:\n",
    "                if record_new[b_l] > record_new[b_r]:\n",
    "                    ret += mid-b_l+1\n",
    "                    tmp.append(record_new[b_r])\n",
    "                    b_r += 1\n",
    "                    # record_new[b_r] = record[b_l]\n",
    "                else:\n",
    "                    tmp.append(record_new[b_l])\n",
    "                    b_l += 1\n",
    "            if b_l <=mid:\n",
    "                tmp.extend([record_new[b] for b in range(b_l,mid+1)])\n",
    "            if b_r <= r:\n",
    "                tmp.extend([record_new[b] for b in range(b_r,r+1)])\n",
    "            record_new[l:r+1] = tmp\n",
    "            return ret\n",
    "        return reverse(0,len(record)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "        def merge_sort(l,r):\n",
    "\n",
    "            if r-l == 1:\n",
    "                return [nums[l]]\n",
    "            m=(r-l)//2+l\n",
    "            left = merge_sort(l,m)\n",
    "            right = merge_sort(m,r)\n",
    "\n",
    "            i=0\n",
    "            j=0\n",
    "            k=r-l\n",
    "            tmp=[]\n",
    "            while(k-i-j>0):\n",
    "                if m+j>=r:\n",
    "                    tmp+=left[i:]\n",
    "                    break\n",
    "                if l+i>=m:\n",
    "                    tmp+=right[j:]\n",
    "                    break\n",
    "            \n",
    "                if left[i]>right[j]:\n",
    "                    tmp.append(right[j])\n",
    "                    self.ans += m-l-i\n",
    "                    j+=1\n",
    "                else:\n",
    "                    tmp.append(left[i])\n",
    "                    i+=1\n",
    "\n",
    "            return tmp\n",
    "\n",
    "        test = []\n",
    "        \n",
    "        if nums:\n",
    "            print(merge_sort(0,len(nums)))\n",
    "        return self.ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums):\n",
    "        if not nums:\n",
    "            return 0\n",
    "        self.n=0\n",
    "        def guibing(l,r):\n",
    "            if l >= r:\n",
    "                return [nums[l]]\n",
    "            m = (l+r)//2\n",
    "            right = guibing(m+1,r)\n",
    "            left = guibing(l,m)\n",
    "            temp = []\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i <= len(right)-1 or j <= len(left)-1:\n",
    "                if i == len(right):\n",
    "                    temp.append(left[j])\n",
    "                    self.n += i\n",
    "                    j += 1\n",
    "                elif j == len(left):\n",
    "                    temp.append(right[i])\n",
    "                    i += 1\n",
    "                elif left[j] <= right[i]:\n",
    "                    temp.append(left[j])\n",
    "                    self.n += i\n",
    "                    j += 1\n",
    "                else:\n",
    "                    temp.append(right[i])\n",
    "                    i += 1\n",
    "            return list(temp)\n",
    "        guibing(0, len(nums) - 1)\n",
    "        return self.n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        # 使用归并排序 计算每一个子数组中比自己小的元素个数 需要记录索引\n",
    "        n = len(nums)\n",
    "        pair = [[nums[i], i] for i in range(n)]\n",
    "        count = [0] * n\n",
    "\n",
    "        def merge_sort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            mid = len(arr) // 2\n",
    "            left = merge_sort(arr[:mid])\n",
    "            right = merge_sort(arr[mid:])\n",
    "            return merge(left, right)\n",
    "\n",
    "        def merge(left, right):\n",
    "            n = len(left) + len(right)\n",
    "            tmp = [0] * n\n",
    "            l, r = 0, 0\n",
    "            for i in range(n):\n",
    "                if l == len(left):\n",
    "                    tmp[i] = right[r]\n",
    "                    r += 1\n",
    "                elif r == len(right):\n",
    "                    count[left[l][1]] += r\n",
    "                    tmp[i] = left[l]\n",
    "                    l += 1\n",
    "                elif left[l][0] <= right[r][0]:\n",
    "                    count[left[l][1]] += r\n",
    "                    tmp[i] = left[l]\n",
    "                    l += 1\n",
    "                elif left[l][0] > right[r][0]:\n",
    "                    tmp[i] = right[r]\n",
    "                    r += 1\n",
    "            return tmp\n",
    "\n",
    "        merge_sort(pair)\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def merge(l, r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            \n",
    "            m = (l+r)//2\n",
    "            res = merge(l,m) + merge(m+1,r)\n",
    "            i, j = l, m+1\n",
    "            for k in range(l,r+1):\n",
    "                tmp[k] = record[k]\n",
    "            \n",
    "            for k in range(l,r+1):\n",
    "                if i==m+1:\n",
    "                    record[k] = tmp[j]\n",
    "                    j+=1\n",
    "                elif j==r+1 or tmp[i]<=tmp[j]:\n",
    "                    record[k] = tmp[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    record[k] =tmp[j]\n",
    "                    j+=1\n",
    "                    res+=(m-i+1)\n",
    "            return res\n",
    "        \n",
    "        tmp = [0]*len(record)\n",
    "        return merge(0, len(record)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        mirror = [0] * len(record)\n",
    "        def dfs(l, r):\n",
    "            nonlocal record, mirror\n",
    "            if l >= r - 1:\n",
    "                return 0\n",
    "            m = l + r >> 1\n",
    "            p, t = l, l\n",
    "            ans = dfs(l, m) + dfs(m, r)\n",
    "            for q in range(m, r):\n",
    "                while p < m and record[p] > record[q]:\n",
    "                    mirror[t] = record[p]\n",
    "                    t += 1\n",
    "                    p += 1\n",
    "                ans += p - l\n",
    "                mirror[t] = record[q]\n",
    "                t += 1\n",
    "            q = t\n",
    "            while p < m:\n",
    "                record[q] = record[p]\n",
    "                q += 1\n",
    "                p += 1\n",
    "            for p in range(l, t):\n",
    "                record[p] = mirror[p]\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, len(record))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        #先用下树状数组，再考虑一下归并算法，归并更像是一种哲学\n",
    "        #先求非逆序对，然后减一下就好了\n",
    "        #这里tree[i]依然对应一个关键区间（二进制位）内的\n",
    "        #树状数组是从小往大的，如果你要每经过一个数就把这个数插入数组\n",
    "        #那你query也就是求前缀和的时候刚好就是前面有多少小于等于他的数(包括自身)\n",
    "        #这里树状数组的索引（位置）是数的大小\n",
    "        #这里因为record数据是分散的，所以你得把他们聚拢，不然update会出错，这也是离散化\n",
    "        n=len(record)\n",
    "        #离散化\n",
    "        myrecord=set()\n",
    "        for num in record:\n",
    "            myrecord.add(num)\n",
    "        myrecord=list(myrecord)\n",
    "        myrecord.sort()\n",
    "        mapping=dict([(val,idx) for idx,val in enumerate(myrecord,1)])\n",
    "        #这里start必须从1开始，不然0会卡死\n",
    "        l=len(mapping)\n",
    "        tree=[0]*(l+10)\n",
    "        def update(i,x):\n",
    "            while i<len(tree):\n",
    "                tree[i]+=x\n",
    "                i+=i&(-i)\n",
    "        def query(i):\n",
    "            s=0\n",
    "            while i:\n",
    "                s+=tree[i]\n",
    "                i-=i&(-i)\n",
    "            return s\n",
    "        temp=0\n",
    "        print(mapping)\n",
    "        for i in range(len(record)):\n",
    "            temp+=query(mapping[record[i]])\n",
    "            update(mapping[record[i]],1)\n",
    "        #这里temp和update的顺序很暧昧啊。。必须先查询，因为要查询之前小于等于这个数的，如果先更新了，那你就会把目前的这个数累加，那就导致你认为它和它自己成为了顺序对，这个不行\n",
    "        return n*(n-1)//2-temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums) -> int:\n",
    "        self.tmp = copy.deepcopy(nums)\n",
    "        self.nums = copy.deepcopy(nums)\n",
    "        def divide(left, right):\n",
    "            if left >= right: return 0\n",
    "            else:\n",
    "                mid = (left + right) // 2\n",
    "                i, j = left, mid+1\n",
    "                count = divide(left, mid) + divide(mid+1, right)\n",
    "                self.tmp[left:right + 1] = self.nums[left:right + 1]\n",
    "                for t in range(left, right+1):\n",
    "                    if j > right:\n",
    "                        self.nums[t] = self.tmp[i]\n",
    "                        i += 1\n",
    "                    elif i > mid:\n",
    "                        self.nums[t] = self.tmp[j]\n",
    "                        j += 1\n",
    "                    elif self.tmp[i] > self.tmp[j]:\n",
    "                        self.nums[t] = self.tmp[i]\n",
    "                        count += (right - j + 1)\n",
    "                        i += 1\n",
    "                    elif self.tmp[i] <= self.tmp[j]:\n",
    "                        self.nums[t] = self.tmp[j]\n",
    "                        j += 1\n",
    "                return count\n",
    "        return divide(0, len(nums)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs1(self, nums: List[int]) -> int:\n",
    "        post = SortedList()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ans += post.bisect_left(nums[i]) # 在左侧查找nums[i]的位置，若不存在则返回可插入位置\n",
    "            print(ans)\n",
    "            post.add(nums[i])\n",
    "            print(post)\n",
    "        return ans\n",
    "    def reversePairs2(self, nums: List[int]) -> int:\n",
    "        def merge_sort(l, r):\n",
    "            # 终止条件\n",
    "            if l >= r: return 0\n",
    "            # 递归划分\n",
    "            m = (l + r) // 2\n",
    "            res = merge_sort(l, m) + merge_sort(m + 1, r)\n",
    "            # 合并阶段\n",
    "            i, j = l, m + 1\n",
    "            tmp[l:r + 1] = nums[l:r + 1]\n",
    "            for k in range(l, r + 1):\n",
    "                if i == m + 1:\n",
    "                    nums[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == r + 1 or tmp[i] <= tmp[j]:\n",
    "                    nums[k] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nums[k] = tmp[j]\n",
    "                    j += 1\n",
    "                    res += m - i + 1 # 统计逆序对\n",
    "            return res\n",
    "        \n",
    "        tmp = [0] * len(nums)\n",
    "        return merge_sort(0, len(nums) - 1)\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def merge_sort(l, r):\n",
    "            # 终止条件\n",
    "            if l >= r: return 0\n",
    "            # 递归划分\n",
    "            m = (l + r) // 2\n",
    "            res = merge_sort(l, m) + merge_sort(m + 1, r)\n",
    "            # 合并阶段\n",
    "            i, j = l, m + 1\n",
    "            tmp[l:r + 1] = nums[l:r + 1]\n",
    "            # for k in range(l, r + 1):\n",
    "            k = l\n",
    "            while i < m + 1 and j < r + 1:\n",
    "                if tmp[i] <= tmp[j]:\n",
    "                    nums[k] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nums[k] = tmp[j]\n",
    "                    j += 1\n",
    "                    res += m - i + 1\n",
    "                k += 1\n",
    "            while i < m + 1:\n",
    "                nums[k] = tmp[i]\n",
    "                i += 1\n",
    "                k += 1\n",
    "            while j < r + 1:\n",
    "                nums[k] = tmp[j]\n",
    "                j += 1\n",
    "                k += 1\n",
    "            return res\n",
    "        \n",
    "        tmp = [0] * len(nums)\n",
    "        return merge_sort(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def reverse(left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            mid = int((right + left) / 2)\n",
    "            res = 0\n",
    "            res += reverse(left, mid) + reverse(mid+1, right)\n",
    "            i = left\n",
    "            j = mid+1\n",
    "\n",
    "            for k in range(left, right+1):\n",
    "                nums[k] = arr[k]\n",
    "\n",
    "            k = i\n",
    "            while k <= right:\n",
    "                if i > mid:\n",
    "                    arr[k] = nums[j]\n",
    "                    j += 1\n",
    "                elif j > right:\n",
    "                    arr[k] = nums[i]\n",
    "                    i += 1\n",
    "                elif nums[i] > nums[j]:\n",
    "                    res += mid - i + 1\n",
    "                    arr[k] = nums[j]\n",
    "                    j += 1\n",
    "                elif nums[i] <= nums[j]:\n",
    "                    arr[k] = nums[i]\n",
    "                    i += 1\n",
    "                k += 1\n",
    "            return res\n",
    "\n",
    "        arr = [nums[i] for i in range(len(nums))]\n",
    "        return reverse(0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def mergesort(left,right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            mid = (left + right) // 2\n",
    "            result = mergesort(left,mid) + mergesort(mid+1,right)\n",
    "            i,j = left, mid+1\n",
    "\n",
    "            temp[left:right+1] = record[left:right+1]\n",
    "\n",
    "            for k in range(left,right+1):\n",
    "                if i == mid + 1:\n",
    "                    record[k] = temp[j]\n",
    "                    j+=1\n",
    "                elif j == right + 1 or temp[i] <= temp[j]:\n",
    "                    record[k]= temp[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    record[k] = temp[j]\n",
    "                    j+=1\n",
    "                    result += mid - i + 1\n",
    "                    \n",
    "            return result\n",
    "\n",
    "        temp = [0] * len(record)\n",
    "        return mergesort(0,len(record) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "        def merge_sort(l, r):\n",
    "            # 终止条件\n",
    "            if l >= r: return 0\n",
    "            # 递归划分\n",
    "            m = (l + r) // 2\n",
    "            res = merge_sort(l, m) + merge_sort(m + 1, r)\n",
    "            # 合并阶段\n",
    "            i, j = l, m + 1\n",
    "            tmp[l:r + 1] = record[l:r + 1]\n",
    "            for k in range(l, r + 1):\n",
    "                if i == m + 1:\n",
    "                    record[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == r + 1 or tmp[i] <= tmp[j]:\n",
    "                    record[k] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    record[k] = tmp[j]\n",
    "                    j += 1\n",
    "                    res += m - i + 1 # 统计逆序对\n",
    "            return res\n",
    "        \n",
    "        tmp = [0] * len(record)\n",
    "        return merge_sort(0, len(record) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, record: List[int]) -> int:\n",
    "\n",
    "        tmp = [0] * len(record)\n",
    "        \n",
    "        def merge_sort(l, r):\n",
    "            \n",
    "            if l >= r: \n",
    "                return 0\n",
    "            m = (l + r)//2\n",
    "            res = merge_sort(l,m) + merge_sort(m+1,r)\n",
    "            i, j = l, m+1\n",
    "            tmp[l:r+1] = record[l:r+1]\n",
    "            for k in range(l,r+1):\n",
    "                if i == m + 1:\n",
    "                    record[k] = tmp[j]\n",
    "                    j += 1\n",
    "                elif j == r + 1 or tmp[i] <= tmp[j]:\n",
    "                    record[k] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    record[k] = tmp[j]# tmp[i] > tmp[j]\n",
    "                    j += 1\n",
    "                    res += m - i + 1 # 统计逆序对\n",
    "            return res\n",
    "\n",
    "        return merge_sort(0,len(record) - 1)  "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
